
template<typename T>
size_t Partition(T* vec,size_t startPos, size_t endPos)
{
	T pivot=vec[endPos];
	size_t i=startPos-1;
	for(size_t j=startPos;j<endPos;j++)
	{
		if(pivot>vec[j])
		{
			++i;
			T temp = vec[i];
			vec[i]=vec[j];
			vec[j]=temp;
		}
	}
	++i;
	T temp = vec[i];
	vec[i]=pivot;
	vec[endPos]=temp;
	return i;
}

template<typename T>
void _QuickSort(T *vec, size_t startPos, size_t endPos)
{
	if(startPos<endPos)
	{
		size_t middle = Partition(vec, startPos,endPos);
		if(middle >startPos)
			_QuickSort(vec,startPos,middle-1);
		if(middle<endPos)
			_QuickSort(vec,middle+1,endPos);
	}
}

template <typename T>
void QuickSort(T* vec, size_t cnt)
{
	_QuickSort(vec,0,cnt-1);
}
